super_palindromes = []

for i in range(1, 10):
    # 奇数位回文数
    if i % 2 == 1:
        bit = i // 2 + 1
        for j in range(pow(10, bit - 1), pow(10, bit)):
            num1 = int(str(j) + str(j)[:-1][::-1])
            num2 = str(pow(num1, 2))
            if num2 == num2[::-1]:
                super_palindromes.append(int(num2))

    # 偶数位回文数
    else:
        bit = i // 2
        for j in range(pow(10, bit - 1), pow(10, bit)):
            num1 = int(str(j) + str(j)[::-1])
            num2 = str(pow(num1, 2))
            if num2 == num2[::-1]:
                super_palindromes.append(int(num2))


class Solution:
    def superpalindromesInRange(self, l: str, r: str) -> int:
        ans = 0
        for super_palindrome in super_palindromes:
            if int(l) <= super_palindrome <= int(r):
                ans += 1
        return ans


if __name__ == "__main__":
    print(Solution().superpalindromesInRange("4", "1000"))  # 4
